/*
* 背包问题：
*   一个背包，可以装很多宝贝，每个宝贝的价值和重量是不一样的，背包也是有承重上限的。
*   要求是在不超过背包承重上限的情况下，尽可能多装价值高的东西
*
* 设：背包的承重上限是h
* 物品：A   B   C  D   E
*
* 价值：12  31  3  32  1
*
* 重量：2   43  1  32  2
* */
let goods = [
    {
        value:12,
        size:2
    },
    {
        value:31,
        size:43
    },
    {
        value:3,
        size:1
    },
    {
        value:32,
        size:32
    },
    {
        value:1,
        size:2
    },
]

//递归解法：
function knapsack1(capactipy,goodsArr,order){ //背包承重 宝贝的数组 宝贝的数量
    if(order < 0 || capactipy <= 0){ //如果宝贝数量为0或者背包承重为0
        return 0 //返回0
    }
    if(goodsArr[order].size > capactipy){ //如果该宝贝重量大于背包承重上限
        return knapsack1(capactipy,goodsArr,order-1)
    }
    return Math.max(
        goodsArr[order].value + knapsack1(capactipy - goodsArr[order].size,goodsArr,order - 1), //要
        knapsack1(capactipy,goodsArr,order - 1) //不要

        //上面一行是该宝贝要装 = 该宝贝价值 + 装宝贝（背包承重 - 该宝贝重量，宝贝数组，宝贝数量 - 1）
        //下面一行是该宝贝不装 = 装宝贝（背包承重，宝贝数组，宝贝数量 - 1）
    )
}

knapsack1(60,goods,4) //承重60 宝贝的数组 宝贝数量（数组从0开始计数）

let goods1 = [
    {
        value:12,
        size:2
    },
    {
        value:31,
        size:43
    },
    {
        value:3,
        size:1
    },
    {
        value:32,
        size:32
    },
    {
        value:1,
        size:2
    },
]

//贪心算法 排序->步骤
function knapsack2(capacity,goodsArr){

    //给宝贝价值排序 从大到小
    goodsArr.sort((a,b) => {
        parseFloat(b.value/b.size) - parseFloat(a.value/a.size)
    })
    console.log(goodsArr)

    let order = goodsArr.length //获取宝贝数量

    let selected = 0 //记录当前选择的最大重量
    let maxValue = 0 //记录当前选择的最大价值

    //步骤
    for(let i = 0; i < order && selected < capacity; i++){ //当宝贝没有遍历完并且背包还能装时
        let {size,value} = goodsArr[i] //解构赋值：重量和价值 = 当前该宝贝对应的重量和价值

        //因为价值已经排好序了，所以能往里面塞就往里面塞
        if(size <= capacity - selected){ //如果当前该宝贝的重量 小于等于 剩下的背包承重
            selected += size //背包承重加上该宝贝重量
            maxValue += value //当前最大价值加上该宝贝价值
        }
    }
    return maxValue
}
knapsack2(60,goods1)


let goods2 = [
    {
        value:12,
        size:2
    },
    {
        value:31,
        size:43
    },
    {
        value:3,
        size:1
    },
    {
        value:32,
        size:32
    },
    {
        value:1,
        size:2
    },
]

//动态规划版
/*
* 状态转移方程：
*   设f（i）（w）为前i件物品在w容量背包里面价值最大 第i件物品的价值为v（i），重量为w（i）
*   f(i)(w) = Math.max(f(i-1)(w),f(i-1)(w - w(i)) + v(i))
*
* 看到41分38秒
*
* */


